Restore IP Addresses

Given a string containing only digits,
restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

题目大意：给定字符串代表无'.'隔开的ip地址，返回所有可能代表的有效的IP地址组合

题目难度：Medium

import java.util.*;
/**
 * Created by gzdaijie on 16/6/5
 * dfs需注意的地方,假定已确定位数k, 待确定 4 - k
 * (1) 剩余的长度应小于等于 (4 - k) * 3
 * (2) 每位数值需要小于 255
 * (3) 每一位除了0外,不能以0开头
 */
public class Solution {
    private List<String> result;

    public List<String> restoreIpAddresses(String s) {
        result = new ArrayList<>();
        if (s.length() < 4) return result;

        String[] tmp = new String[4];
        ipAddressesDfs(tmp, 0 , s, 0);
        return result;
    }

    private void ipAddressesDfs(String[] tmp, int index, String s, int k) {
        if (index == 4) {
            result.add(tmp[0] + "." + tmp[1] + "." + tmp[2] + "." + tmp[3]);
            return;
        }

        int len = s.length();
        int sum;
        for (int j = 1; j <= 3 && k + j <= len; j++) {
            // 剩余的字符串长度不能超过 3 * (3 - index), index从0开始
            if (len - k - j > 3 * (3 - index)) continue; 

            tmp[index] = s.substring(k, k + j);
            sum = Integer.parseInt(tmp[index]);
            if (sum > 255 ) continue; // 不能大于255
            if (j != 1 && tmp[index].charAt(0) == '0') break; // j > 1,不能以0开头

            ipAddressesDfs(tmp, index + 1, s, k + j);
        }
    }
}